#include <stdlib.h>
#include <stdio.h>
typedef struct BTNode{
    int data;
    BTNode * left;
    BTNode * right;
}BTNode;
BTNode * CreatBTree(int a[],int n){
    BTNode * root;
    BTNode * c;
    BTNode * pa;
    BTNode * p;
    root=(BTNode *)malloc(sizeof(BTNode));
    root->data=a[0];
    root->left=root->right=NULL;
    for(int i=1;i<n;i++){
        p=(BTNode *)malloc(sizeof(BTNode));
        p->data=a[i];
        p->left=p->right=NULL;
        c=root;
        while(c){
            pa=c;
            if(c->data>p->data)
                c=c->left;
            else
                c=c->right;
        }
        if(p->data<pa->data)
            pa->left=p;
        else
            pa->right=p;
    }
    return root;
}
void PreOrder1(BTNode * root){
    BTNode ** s = (BTNode ** )malloc(sizeof(BTNode *) * 10);
    int top = -1;
    BTNode * p = root;
    while(p||top!=-1){
        if(p){
            s[++top] = p;
            printf("%5d",p->data);
            p=p->left;
        }
        else{
            p = s[top--];
            p = p->right;
        }
    }
    free(s);
}
void PreOrder2(BTNode * root){
    BTNode ** s = (BTNode ** )malloc(sizeof(BTNode *) * 10);
    int top = -1;
    BTNode * p = root;
    s[++top] = p;
    while(top != -1){
        p = s[top--];
        printf("%5d",p->data);
        if(p->right)
            s[++top] = p->right;
        if(p->left)
            s[++top] = p->left;
    }
}
void InOrder(BTNode * root){
    BTNode ** s = (BTNode ** )malloc(sizeof(BTNode *) * 10);
    int top = -1;
    BTNode * p = root;
    while(top != -1||p){
        if(p){
            s[++top] = p;
            p = p->left;
        } else{
            p = s[top--];
            printf("%d",p->data);
            p = p->right;
        }
    }
}
int main(void){
    int a[9]={6,5,7,9,2,4,3,8,1};
    BTNode * root=CreatBTree(a,9);
    InOrder(root);
    PreOrder1(root);
    PreOrder2(root);
}